#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <unordered_map>
#include <vector>
//int main() {
//    int n;
//    cin >> n;
//    unordered_map<char, int> m;
//    vector<char> s(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> s[i];
//    }
//    int sum = 0;
//    for (int i = 0; i < n; i++)
//    {
//        if (s[i] == 's')
//        {
//            for (int j = i + 1; j < n; j++)
//                m[s[j]]++;
//            int num_h = m['h'];
//            int num_y = m['y'];
//            sum += num_h * num_y;
//            m['h'] = 0;
//            m['y'] = 0;
//        }
//        cout << sum << endl;
//    }
//    return 0;
//}
//class Solution {
//public:
//    void sortColors(vector<int>& nums) {
//        int left = -1;
//        int right = nums.size();
//        for (int i = 0; i < right;)
//        {
//            if (nums[i] == 0)
//            {
//                swap(nums[++left], nums[i++]);
//            }
//            else if(nums[i] == 2)
//            {
//                swap(nums[--right], nums[i]);
//            }
//            else
//            {
//                i++;
//            }
//        }
//    }
//};

//class Solution {
//public:
//    void dfs(vector<int>& nums, int left, int right)
//    {
//        if (left >= right)
//            return;
//        int begin = left;
//        int end = right;
//        int key = nums[left];
//        while (begin < end)
//        {
//            while (begin<end && nums[end]>key)
//            {
//                end--;
//            }
//            while (begin < end && nums[begin] < key)
//            {
//                begin++;
//            }
//            swap(nums[begin], nums[end]);
//        }
//        swap(nums[begin], nums[left]);
//
//        dfs(nums, left, begin - 1);
//        dfs(nums, begin + 1, right);
//    }
//    vector<int> sortArray(vector<int>& nums) {
//        dfs(nums, 0, nums.size() - 1);
//        return nums;
//    }
//};

class Solution {
public:
    void dfs(vector<int>& nums, int begin, int end)
    {
        if (begin >= end)
            return;
        int left = -1;
        int right = end + 1;
        int key = nums[begin];
        for (int i = 0; i < right;)
        {
            if (nums[i] < key)
                swap(nums[i++], nums[++left]);
            else if (nums[i] > key)
                swap(nums[i], nums[--right]);
            else
                i++;
        }
        dfs(nums, begin, left - 1);
        dfs(nums, right + 1, end);

    }
    vector<int> sortArray(vector<int>& nums) {
        dfs(nums, 0, nums.size() - 1);
        return nums;
    }
};
int main()
{
    Solution s;
    vector<int> nums = { 5,2,3,1 };
    /*s.sortColors(nums);*/
    s.sortArray(nums);
    return 0;
}